#include "StdAfx.h"
#include "StringApp.h"


StringApp::StringApp(void)
{
}


StringApp::~StringApp(void)
{
}

char StringApp::PopQueue(queue<char>& charQueue){
	if(charQueue.empty()){
		return ' ';
	}
	char popChar = charQueue.front();
	charQueue.pop();
	return popChar;
}

void StringApp::PushQueue(queue<char>& charQueue,char c){
	charQueue.push(c);
	
}

void StringApp::AllComposite(char* strArray,int length){
	
	char* newString = new char[length];
	for(int i = 0;i<length;i++){
		newString[i] = ' ';
	}
	int hash[256] = {0};
	CompositeRecursion(strArray,newString,length,0,hash);
}

void StringApp::CompositeRecursion(char* oldString,char* newString,int length,int index,int* hash){
	if(index >length){
		return;
	}
	bool skip = false;
	//cout<<"oldString="<<oldString<<";newString="<<newString<<endl;
	for(int i = 0;i<=1;i++){
		//if(hash[oldString[index]] < 1){
		if(i == 0){
			newString[index] = oldString[index];
			hash[oldString[index]] = 1; 
		}else{
			newString[index] = ' ';
		}
		for(int j = index-1;j>=0;j--){
			if(oldString[j] == oldString[index]){
				newString[index] = ' ';
				skip = true;
				i++;
			}
		}
		
		//}else{
		//	newString[index] = ' ';
		//	hash[oldString[index]] += 1;
		//		i++;
		//	}
		
		CompositeRecursion(oldString,newString,length,index+1,hash);
		
		if(index == length-1){
			//if(!skip){
				PrintSpaceString(newString,length);
			//}
			
			
		}
		hash[oldString[index]] -= 1;
	}
	
	

}

void StringApp::PrintSpaceString(char* printString,int length){
	for(int i = 0;i<length;i++){
		if(printString[i] != ' '){
			cout<<printString[i];
		}
	}
	cout<<'\t';
}

void StringApp::AllRank(char* strArray,int length){
	if(strArray == NULL){
		return;
	}
	RankRecursion(strArray,length,0);
}

void StringApp::RankRecursion(char* strArray,int length,int index){
	
	if(index>=length){
		return;
	}
	char tempChar=' ';
	
	for(int i = index;i<length;i++){
		//cout<<"tempChar="<<tempChar<<";i="<<i<<endl;
		/*int status = 0;
		for(int j = index;j<i;j++){
			if(strArray[index] == strArray[j]){
				status = 1;
				break;
			}
		}*/
		if(strArray[index] == strArray[i] && i != index){
			continue;
		}
		
		tempChar = strArray[index];
		strArray[index] = strArray[i];
		strArray[i] = tempChar;
		
		RankRecursion(strArray,length,index+1);
		
		if(index == length -1){
			cout<<strArray<<'\t';
		}

		tempChar = strArray[index];
		strArray[index] = strArray[i];
		strArray[i] = tempChar;
	}
}

void StringApp::PrintArray(int* intArray,int length){
	for(int i = 0;i<length;i++){
		cout<<intArray[i]<<"  ";
	}
	cout<<endl;
}

void StringApp::LisPrint(int* origArray,int length){
	int* lengthArray = new int[length]; 
	
	for(int i = 0;i<length;i++){
		int index = i-1;
		int tempLength = 0;
		while(index>=0){
			if(origArray[index]<origArray[i]){
				if(lengthArray[index]>tempLength){
					tempLength = lengthArray[index];
				}
			}
			index--;
		}
		lengthArray[i] = tempLength+1;
	}
	int maxLength = 0;
	for(int i = 0;i<length;i++){
		if(lengthArray[i]>maxLength){
			maxLength = lengthArray[i];
		}
	}
	PrintArray(lengthArray,length);
	cout<<"maxLength = "<<maxLength<<endl;
}

void StringApp::EditDistance(char* firstString,int firstLength,char* secondString,int secondLength){
	if(firstString == NULL || secondString == NULL){
		return;
	}

	int** distanceArray;
	distanceArray = new int*[secondLength];
	for(int i = 0;i<secondLength;i++){
		distanceArray[i] = new int[firstLength];
	}
	distanceArray[0][0] = 0;
	for(int i = 0;i<firstLength;i++){
		for(int j = 0;j<secondLength;j++){
			distanceArray[j][i] = 0;
		}
	}
	for(int i = 0;i<firstLength;i++){
		distanceArray[0][i] = i;
	}
	for(int i = 0;i<secondLength;i++){
		distanceArray[i][0] = i;
	}

	for(int i = 1;i<secondLength;i++){
		for(int j = 1;j<firstLength;j++){
			int dialog = distanceArray[i-1][j-1]+CompareDistance(firstString[j],secondString[i]);
			cout<<"j="<<j<<";dialog="<<dialog<<";left="<<distanceArray[i][j-1]<<";up = "<<distanceArray[i-1][j]<<endl;
			int min = EditMin(dialog,distanceArray[i][j-1]+1,distanceArray[i-1][j]+1);
			
			distanceArray[i][j] = min;
		}
	}

	for(int i = 0;i<secondLength;i++){
		for(int j = 0;j<firstLength;j++){
			cout<<distanceArray[i][j]<<"  ";
		}
		cout<<endl;
	}
	
}
int StringApp::EditMin(int dialog,int up,int left){
	cout<<"dialog="<<dialog<<";left="<<left<<";up = "<<up<<endl;
	if(dialog<up){
		if(dialog<left){
			return dialog;
		}else{
			return left;
		}
	}else{
		if(up<left){
			return up;
		}else{
			return left;
		}
	}
}
int StringApp::CompareDistance(char ver,char hor){
	if(ver == hor){
		return 0;
	}
	return 1;
}

void StringApp::MinString(){
	char** stringArray = new char*[3];
	stringArray[0] = "321";
	stringArray[1] = "325";
	stringArray[2] = "31";

	QsortString(stringArray,0,2);
}

void StringApp::QsortString(char** strArray,int begin,int end){
	if(begin>end){
		return;
	}

	int index = ParitionString(strArray,begin,end);
	QsortString(strArray,begin,index);
	QsortString(strArray,index,end);
}

int StringApp::ParitionString(char** strArray,int begin,int end){

	int index = (begin+end)/2;

	string str1 = strArray[begin];
	string str2 = strArray[end];
	string str12 = str1+str2;
	string str21 = str2+str1;

	/*if(strcmp(str12,str21)<0){

	}else if(strcmp(str12,str21)>0){

	}else{
	}*/
	
	cout<<str12;
	return 0;
}

int StringApp::StrToInt(char* intChar,int length){
	if(intChar == NULL){
		return 0;
	}
	int num = 0;
	bool minus = false;
	if(intChar == "+" || intChar == "-"){
		return 0;
	}

	if(intChar[0] == '-'){
		minus = true;
		intChar = &intChar[1];
	}else if(intChar[0] == '+'){
		intChar = &intChar[1];
	}
	num = GetInt(intChar,length);
	if(minus){
		num = 0-num;
	}
	cout<<"num="<<num<<endl;
}

int StringApp::GetInt(char* intChar,int length){
	long long num = 0;
	for(int i = 0;i<length;i++){
		num = (num *10+(intChar[i]-'0'));
		cout<<"num="<<num<<";intChar[i]="<<intChar[i]<<endl;
		if(num > 0x7fffffff){
			return 0;
		}
		throw exception("wrong num");
	}
	return num;
}